class Solution:
    def sortArray(self, nums: list) -> list:
        """快速排序
        """
        self.quickSort(nums, 0, len(nums) - 1)
        return nums

    def quickSort(self, array: list, left: int, right: int):
        if left < right:
            key = array[right]
            i = left
            j = right - 1
            while True:
                while array[i] < key:
                    i += 1
                while j >= 0 and array[j] > key:
                    j -= 1
                if i < j:
                    self.swap(array, i, j)
                else:
                    break
            self.swap(array, i, right)
            self.quickSort(array, left, i - 1)
            self.quickSort(array, i + 1, right)

    def swap(self, array, i, j):
        temp = array[i]
        array[i] = array[j]
        array[j] = temp
